home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 20 / Cream of the Crop 20 (Terry Blount) (1996).iso / disk / pgpmnu31.zip / PKE-RSA.TXT < prev    next >
Text File  |  1996-05-05  |  16KB  |  471 lines
  1.                         PKE - PUBLIC KEY ENCRYPTION
  2.  
  3.      This paper heavily relies on Bruce Schneier's excellent
  4.      book, Applied Cryptography: Protocols, Algorithms and
  5.      Source Code in C, cited at the end of the text.
  6.  
  7.                              Table of Contents
  8.  
  9.           Introduction
  10.           RSA Encryption
  11.           A Quick Runthrough
  12.           Modular Arithmetic
  13.           The Extended Euclid's Algorithm
  14.           Fermat's Little Theorem
  15.           Euler's Totient Function
  16.           The Inner Workings
  17.  
  18.  
  19.                                INTRODUCTION
  20.      
  21.      The first Public Key Encryption algorithm was invented by
  22. Whitfield Diffie and Martin Hellman at Stanford University.  They
  23. and independently Ralph Merkle invented the concept in 1976.  The
  24. advantage of PKE is that it avoids the problem of securely
  25. transmitting secret keys.  
  26.  
  27.      PKE relies on the difficulty of factoring a very large
  28. number.  The public and private keys are functions of a pair of
  29. large prime numbers, 100 to 300 digits.  Recovering the plaintext
  30. from the keys and the ciphertext is equivalent to factoring the
  31. product of two primes, 
  32.  
  33.           n = p * q
  34.  
  35. or by repeated encryption, which will be explained later, but
  36. mandates that the product (p - 1) * (q - 1) should have no small
  37. factors.
  38.      
  39.      Using a 512 bit value for n gives a number of 154 digits; a
  40. 1028 bit value for n gives a number of 308 digits.  A 40 digit
  41. number can today be factored in a matter of hours, but it takes a
  42. tenfold increase in computing power to factor a number with each
  43. increase of 10 digits.  A 664 bit number of 200 digits takes
  44. 10^23 operations to factor (an operation is a complex iteration
  45. of the factoring algorithm, not a simple microcomputer
  46. operation).  Assuming a super computer can perform a million
  47. operations per second, and that a network of a million such
  48. computers is assigned the task, it will take 3700 years to factor
  49. the 200 digit number.  If n is a 1024 bit number (like the
  50. product of two primes of 512 bits each) that same array of
  51. computers will take 10^10 years to factor the 308 digit number,
  52. and the universe has not yet existed that long.  
  53.  
  54.  
  55.                               RSA ENCRYPTION
  56.  
  57.      The RSA algorithm is named after its three inventors, Ron
  58. Rivest, Adi Shamir, and Leonard Adleman, who first introduced the
  59. algorithm in 1978.  It is patented.
  60.  
  61. The Public Key, used to encrypt a message intended for its owner,
  62. consists of two numbers, n and e.
  63.  
  64.           n - the product of two primes, p and q 
  65.               (p and q must remain secret)                  
  66.                                                                  
  67.           e - a number chosen at random which is relatively prime
  68.               to (p-1) * (q-1) 
  69.                                                        
  70.      The Secret Key, d, used to decrypt a cyphertext and restore
  71. a message by its owner, is one number, and we will see why it is
  72. in this form in the section on the inner workings.  
  73.  
  74.           (d * e) (mod (p-1) * (q-1)) = 1    
  75.  
  76. or   
  77.  
  78.           d ≡ e^-1 (mod (p-1) * (q-1))                 
  79.  
  80. To encrypt a message m and create a cyphertext c 
  81.                                                        
  82.           c = m^e (mod n)                                   
  83.                                                        
  84. To decrypt a cyphertext c and restore the message m 
  85.  
  86.           m = c^d (mod n)                                   
  87.      
  88.  
  89.                             A QUICK RUNTHROUGH
  90.  
  91.      For those already familiar with number theory, This quick
  92. runthrough will demonstrate the mathematics of the RSA algorithm
  93. fro those already familiar with number theory and give others an
  94. initial overview of the procedure.  The complete mathematical
  95. framework will be introduced from the ground up following this
  96. quick runthrough.  
  97.  
  98.      To generate the public and private keys, choose two large
  99. prime numbers, p and q.  Compute the product:
  100.  
  101.           n = p * q
  102.  
  103. Example:  If p = 47  and  q = 71
  104.  
  105.           n = p * q = 3337
  106.  
  107. Then randomly choose the encryption key e, such that e and 
  108. (p-1) * (q-1) are relatively prime (have no factors in common). 
  109. Finally, use the extended Euclid's algorithm or Euler's totient
  110. function to compute the decryption key d by the inverse modululo
  111. function, such that
  112.  
  113.           d ≡ e^-1 (mod (p - 1) * (q - 1))
  114.  
  115. and this equation is equivalent to
  116.  
  117.           d * e = (p -1) * (q - 1) * k + 1
  118.  
  119. Example:  If e is chosen to be 79
  120.  
  121.           79 * d = 3220 * k + 1
  122.  
  123.           d ≡ 79^-1 (mod (71 - 1) * (47 - 1)) 
  124.  
  125.           d ≡ 79^-1 mod 3220 = 1019
  126.  
  127.      Note that d and e are relatively prime.  The two primes p
  128. and q are no longer needed.  They can be discarded, but should
  129. never be revealed.
  130.  
  131.      To encrypt a message m, first divide it into numerical
  132. blocks such that each block is smaller than n and therefore has a
  133. unique representation modulo n.  Choose With binary data, choose
  134. the largest power of 2 less than n.  The encrypted message c will
  135. be made up of similarly sized message blocks of about the same
  136. length:
  137.  
  138.           c = m^e mod n
  139.  
  140. Example: Let's say the message m is 6882326879666683.  First
  141. break it into blocks.  n is 3337, a four digit number, so three
  142. digit blocks will work nicely in this case.  The first block is
  143. encrypted as: 
  144.  
  145.           c = 688^79 mod 3337 = 1570
  146.  
  147. To decrypt a message, take each encrypted block c and compute:
  148.  
  149.           m = c^d mod n
  150.  
  151. Example: Decrypting the first block requires performing the same
  152. exponentiation using the decryption key of 1019.
  153.  
  154.           m = 1570^1019 mod 3337 = 688 
  155.  
  156. Of course, your calculator can't deal with a number whose
  157. exponent is 1019, but we will see how the exponent can be
  158. partitioned and dealt with in smaller bites.
  159.  
  160.  
  161.                             MODULAR ARITHMETIC
  162.  
  163.      If r equals the remainder of d divided by n, modular
  164. arithmetic expresses this as
  165.  
  166.           d mod n = r              or   d ≡ r mod n
  167.  
  168. The first equation is read, "d mod (or modulo) n equals r," and
  169. the second is read, "d is congruent to r mod (or modulo) n." 
  170.  
  171. Example:  1026 mod 7 = 4           or   1026 ≡ 4 mod 7
  172.  
  173. These equations are equivalent to 
  174.  
  175.           1026 / 7 = 146 + 4
  176.  
  177.      If you depart by plane at 7:00pm and arrive at your
  178. destination 9 hours later, what time does your watch say before
  179. setting it to your new time zone?
  180.  
  181.           (7 + 9) mod 12 = 4  Your watch says 4:00am.
  182.  
  183.      Modular arithmetic can be added, subtracted, multiplied and
  184. exponentiated, the equivalent of repeated multiplication.  The
  185. ability to manipulate the exponents helps when dealing with the
  186. large exponents we encounter in PKE.  There is an example in the
  187. section on the inner workings.
  188.  
  189.           (x + y) mod n = ((x mod n) + (y mod n)) mod n
  190.  
  191.           (x - y) mod n = ((x mod n) - (y mod n)) mod n
  192.  
  193.           (x * y) mod n = ((x mod n) * (y mod n)) mod n
  194.  
  195.           x^3y mod n = ((x^y mod n) * (x^2y mod n)) mod n
  196.      
  197. One cannot divide congruences in all cases, 
  198.  
  199.           16 ≡ 6 mod 10 is not equal to  8 ≡ 3 mod 10.
  200.  
  201.      Any pair of relatively prime integers (having no factors in
  202. common) has the remarkable property that multiples of each can
  203. always be found such that their difference is unity.  Stated
  204. another way, there always exists some multiple of an integer, n,
  205. which leave a remainder of one when divided by another integer
  206. prime to it, and the multiplier of n is always a smaller number
  207. than the divisor of the product.  For 15 and 11, there exists two
  208. integers x and y, such that 
  209.  
  210.           (15 * x) - (11 * y) = 1  or   15 * x = 11 * y + 1
  211.  
  212. This property brings us to the inverse modulo function.
  213.  
  214.                       THE EXTENDED EUCLID'S ALGORITHM  
  215.  
  216.      The inverse modulo function is equivalent to finding a
  217. number d, such that 
  218.  
  219.           (y * x) mod n = 1        or   y * x ≡ 1 mod n
  220.  
  221. Example:  (15 * d) mod 11 = 1      or   15 * d ≡ 1 mod 11
  222.  
  223. The inverse of a number is that number which multiplied by the
  224. original number gives one as the product.  The inverse